/*
 * CliqueLifter.cpp
 *
 *  Created on: Sep 24, 2014
 *      Author: correa
 */

#include <CliqueLifter.h>
#include <unordered_map>

CliqueLifter::CliqueLifter(Grafo &grafo, Cliquer &cliquer) :
		_grafo(grafo), _cliquer(cliquer), _unionvecindades(), _candidatos(_grafo.getN())
{
}

CliqueLifter::~CliqueLifter() {
	while (!_unionvecindades.empty())
	{
		VertexSet * d = _unionvecindades.back();
		_unionvecindades.pop_back();
		delete d;
	}
}

bool CliqueLifter::lift(Desigualdad *dv, VertexSet *W)
{
	int lambda = calculaLambda(dv->getSoporte(), dv->getCoeficientes(), *W, dv->getRHS());

	if (lambda != 0)
	{
		int nuevoCoef;
		for (VertexSetIterator it = W->begin(); it != W->end(); ++it)
		{
			nuevoCoef = dv->getCoeficiente(*it) + lambda;
			dv->setCoeficiente(*it, nuevoCoef);
			if (nuevoCoef > 1)
				dv->setAsNotRank();
		}

		dv->setRHS(dv->getRHS()+lambda);
	}

	return (lambda > 0);
}

bool CliqueLifter::lift(Desigualdad * ret, vector<CliqueProyectada*> proyecciones) {
	int ncliques = proyecciones.size()-1;
	int lambda = 0;

	if (ncliques > 0)
	{
		VertexSet unioncliques(_grafo.getN());
		for (int i = 0; i < ncliques; ++i)
			unioncliques.addAll(*proyecciones[i]);
		VertexSet concoef(unioncliques);
		unioncliques.addAll(*proyecciones[ncliques]);
		concoef.retainAll(ret->getSoporte());
		VertexSet Rconcoef(_grafo.getN());

		int maxsop = 0;

		for (int i = _unionvecindades.size(); i < ncliques; ++i)
			_unionvecindades.push_back(new VertexSet(_grafo.getN()));

		unordered_map<_CPLUSPLUSBITSET_,int> recipe;
		recipe.max_load_factor(0.5);

		int vertex[ncliques];
		int stack[ncliques+1];
		int level = 0;
		int top = 0;
		stack[top] = -1;
		vertex[level] = -1;
		int v;
		int valor = 0;
		VertexSet stableset(_grafo.getN());
		ProjectableCliqueSet _RR(_grafo.getN());
		_candidatos.copyAll(*proyecciones[level]);
		_candidatos.removeAll(*proyecciones[ncliques]);
		while (level >= 0 && level < ncliques)
		{
			VertexSetIterator itv = _candidatos.begin(vertex[level]+1);
			if (itv == _candidatos.end())
				v = -1;
			else
			{
				int cov;
				if (level > 5 && valor + ret->getCoeficiente(v) + maxsop <= lambda)
				{
					if (maxsop == 0)
						maxsop = calculaLambda(ret->getSoporte(), ret->getCoeficientes(), unioncliques, ret->getRHS());

					do {
						v = *itv;

						cov = 0;
						Rconcoef.copyAll(concoef);
						for (int i = 1; i <= top; ++i)
						{
							Rconcoef.remove(vertex[stack[i]]);
							Rconcoef.removeAll(_grafo.vecinos(vertex[stack[i]]));
						}
						Rconcoef.remove(v);
						Rconcoef.removeAll(_grafo.vecinos(v));
						for (int i = level+1; i < ncliques; ++i)
						{
							if (Rconcoef.intersects(*proyecciones[i]))
							{
								VertexSet inters(Rconcoef);
								inters.retainAll(*proyecciones[i]);
								int max = 0;
								for (VertexSetIterator ii = inters.begin(); ii != inters.end(); ++ii)
									if (ret->getCoeficiente(*ii) > max)
										max = ret->getCoeficiente(*ii);
								cov += max;
								Rconcoef.removeAll(*proyecciones[i]);
							}
						}
					}
					while (level > 5 && valor + ret->getCoeficiente(v) + cov + maxsop <= lambda && ++itv != _candidatos.end());
				}
				else
					v = *itv;
				if (itv == _candidatos.end())
				{
//					cout << "Soporte: ";
//					ret->getSoporte().print();
//					unioncliques.print();
//					cout << "UUUAUAUAUAUAUAUUUAUAUAUAUUUAUAUAUAUAUUUUAU  maxsop=" << maxsop << " cov=" << cov << " lambda=" << lambda << " level=" << level << endl;
//					for (int i = 1; i <= top; ++i)
//						cout << " " << vertex[stack[i]];
//					cout << endl;
//					cout << "level=" << level << " v=" << v << " top of stack=" << stack[top] << endl;
					v = -1;
				}
				else
				{
					_unionvecindades[level]->copyAll(_grafo.vecinos(v));
					_unionvecindades[level]->add(v);
					if (top > 0)
						_unionvecindades[level]->addAll(*_unionvecindades[stack[top]]);
					else
						_unionvecindades[level]->addAll(*proyecciones[ncliques]);
				}
			}
//			cout << "level=" << level << " v=" << v << " top of stack=" << stack[top] << endl;
			if (v >= 0)
			{
				stableset.add(v);
				vertex[level] = v;
				stack[++top] = level;
				valor += ret->getCoeficiente(v);
				while (++level < ncliques && proyecciones[level]->intersects(stableset));
				if (level < ncliques)
				{
					vertex[level] = -1;
					_candidatos.copyAll(*proyecciones[level]);
					_candidatos.removeAll(*_unionvecindades[stack[top]]);
				}
			}
			// cout << "level=" << level << " v=" << v << " top of stack=" << stack[top] << endl;
			if (v < 0 || level == ncliques)
			{
				if (level == ncliques)
				{
//					cout << "stable set: [";
//					for (int a = 1; a <= top; a++)
//						cout << " " << vertex[stack[a]];
//					cout << " ]" << endl;

					VertexSet keyset(ret->getSoporte());
					keyset.removeAll(*_unionvecindades[stack[top]]);
					_CPLUSPLUSBITSET_ key = keyset.toBitset();
					unordered_map<_CPLUSPLUSBITSET_,int>::const_iterator value = recipe.find(key);
					int mj;
					if (value != recipe.end())
						mj = value->second;
					else
					{
						mj = calculaLambda(ret->getSoporte(), ret->getCoeficientes(), *_unionvecindades[stack[top]], ret->getRHS());
						pair<_CPLUSPLUSBITSET_,int> p(key,mj);
						recipe.insert(p);
					}
//					cout << "mj=" << mj << endl;

					if (valor+mj > lambda)
						lambda = valor+mj;
				}
				level = stack[top--];
				if (level >= 0)
				{
					stableset.remove(vertex[level]);
					valor -= ret->getCoeficiente(vertex[level]);
					_candidatos.copyAll(*proyecciones[level]);
					if (top > 0)
						_candidatos.removeAll(*_unionvecindades[stack[top]]);
					else
						_candidatos.removeAll(*proyecciones[ncliques]);
				}
			}
		}
	}
	else
		lambda = calculaLambda(ret->getSoporte(), ret->getCoeficientes(), *proyecciones[ncliques], ret->getRHS());

//	cout << "Lambda: " << lambda << " rhs: " << ret->getRHS() << endl;

	if (lambda != 0)
	{
		int nuevoCoef;
		for (VertexSetIterator it = proyecciones[ncliques]->begin(); it != proyecciones[ncliques]->end(); ++it)
		{
			nuevoCoef = ret->getCoeficiente(*it) + lambda;
			ret->setCoeficiente(*it, nuevoCoef);
			if (nuevoCoef > 1)
				ret->setAsNotRank();
		}

		ret->setRHS(ret->getRHS()+lambda);
	}

	return (lambda > 0);

}
